package com.sicheng.lc.杂题.前缀和之异或篇;

import java.util.HashMap;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/11/17 16:59
 */
public class 最长偶数次组成子串 {
    //给定一个由N个小写字符组成的字符串S，任务是找出由偶数次组成的最长子字符串的长度
    // 目标子串的所有字符均出现偶数次
    // 1 <= n <= 1e5

    // 大致思路
    // 1. 将字符压缩到32位数里
    // 2. 利用前缀和思想 把当前的遍历的子串s[0,j]，压缩到cur
    // 3. 由于目标是所有字符均出现偶数次，那么目标的异或总和为0
    // 4. 当前s[0,j] 期待一个以前遍历过的s[0,i] 使得s[i,j]的异或和为0

    // 字符压缩到2进制：2进制只有2个状态1表示含有，0表示不含有
    // 将26个字母[a,z]标号[0,25]压缩到对应的位中
    // 5 <===> 1001b ====>第0位是1，第3位也是1那么 a,d就会被压缩成5
    // 异或：2进制位里相同的位变成0，不同的位表示1
    //时间复杂度O(N),空间复杂度大约是O(N)额外的空间：hash表  一个int32 以及一个res
    int longest(String s) {
        int max = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int cur = 0;
        for (int i = 0; i < s.length(); i++) {
            cur ^= 1 << (s.charAt(i) - 'a');
            if (!map.containsKey(cur)) {
                map.put(cur, i);
            } else {
                max = Math.max(max, i - map.get(cur));
            }
        }
        return max;
    }


    public static void main(String[] args) {
        最长偶数次组成子串 s = new 最长偶数次组成子串();
        System.out.println(s.longest("bdaaadadb"));
        System.out.println(s.longest("zthtzh"));
        System.out.println(s.longest("abacd"));
    }
}
